76 最小覆盖子串

https://leetcode.cn/leetbook/read/top-interview-questions-hard/xw1tws/

cost: 54m49s

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> freqs;
        for (const char ch : t) {
            freqs[ch]++;
        }

        vector<int> res = {0, -1};
        unordered_map<char, int> currFreqs;
        int left = 0, right = 0;
        while (right < s.size()) {
            char ch = s[right];
            if (!freqs.count(ch)) {
                right++;
                continue;
            }
            currFreqs[ch]++;
            if (this->check(freqs, currFreqs)) {
                while (!freqs.count(s[left])) {
                    left++;
                }
                currFreqs[s[left]]--;
                while (this->check(freqs, currFreqs)) {
                    left++;
                    currFreqs[s[left]]--;
                }
                currFreqs[s[left]]++;
                if (res[1] == -1 || (right - left < res[1] - res[0])) {
                    res[0] = left;
                    res[1] = right;
                }
            }
            right++;
        }
        return s.substr(res[0], res[1] - res[0] + 1);
    }

private:
    bool check(unordered_map<char, int>& freqs,
               unordered_map<char, int>& currFreqs) {
        for (auto [key, cnt] : freqs) {
            if (!currFreqs.count(key)) {
                return false;
            }
            if (currFreqs[key] < cnt) {
                return false;
            }
        }
        return true;
    }
};